<!DOCTYPE html>
<html manifest="cache.appcache">
  <head>
    <meta charset="utf-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=Edge;chrome=1" />
    <title>Lexical Scanning in Go</title>
    <link href="http://fonts.googleapis.com/css?family=Droid+Sans|Droid+Sans+Mono" rel="stylesheet" type="text/css" />
    <link id="prettify-link" href="src/prettify/prettify.css" rel="stylesheet" disabled />
    <link href="css/default.css" class="theme" rel="stylesheet" media="screen"  />
    <link href="css/common.css" rel="stylesheet" media="screen" />
  </head>
  <body>
    <nav id="helpers">
      <button title="Previous slide" id="nav-prev" class="nav-prev">⇽</button> 
      <button title="Jump to a random slide" id="slide-no">5</button> 
      <button title="Next slide" id="nav-next" class="nav-next">⇾</button>
      <menu>
        <button type="checkbox" data-command="toc" title="Table of Contents" class="toc">TOC</button>
        <button type="checkbox" data-command="notes" title="View Slide Notes">✏</button>
        <button type="checkbox" data-command="source" title="View slide source">↻</button>
        <button type="checkbox" data-command="help" title="View Help">?</button>
      </menu>
    </nav>
    <div class="presentation">
      <div id="presentation-counter">Loading...</div>
      <div class="slides">
        <div class="slide" id="landing-slide">
          <style>
            #landing-slide p {
              font-size: 35px;
            }
          </style>
          <section class="middle">
            <p>This presentation is an HTML5 web site</p>
            <p>Press <span id="left-init-key" class="key">&rarr;</span> key to advance.</p>
          </section>

          <aside class="note">
            <section>
              Welcome! (This field is for presenter notes and commentary.)
            </section>
          </aside> 
        </div>

        <div class="slide" id="controls-slide">
          <header>Controls</header>
          <style>
            #controls-slide li, #controls-slide p {
              font-size: 32px;
            }
            #controls-slide .key {
              bottom: 2px;
            }
          </style>
          <section>
            <ul>
              <li><span class="key">&larr;</span> and <span class="key">&rarr;</span> to move around.</li>
              <li><span class="key">Ctrl/Command</span> and <span class="key">+</span> or <span class="key">-</span> to zoom.</li>
              <li><span class="key">S</span> to view page source.</li>
              <li><span class="key">N</span> to toggle speaker notes.</li>
              <li><span class="key">3</span> to toggle 3D effect.</li>
              <li><span class="key">0</span> to toggle help.</li>
            </ul>
          </section>
        </div>

        <div class="slide" id="hello">
          <section class="middle">
            <hgroup><img src="http://golang.org/doc/gopher/bumper640x360.png"></hgroup>
          </section>
        </div>

        <div class="slide" id="title-slide">
          <style>
            #title-slide h1, #title-slide h2 {
              color: black;
            }
            #title-slide h1 {
              font-size: 80px;
            }
            #title-slide h2 {
              font-size: 36px;
            }
          </style>
          <section class="middle">
            <hgroup>
              <h1>
                Lexical Scanning in Go
              </h1>
              <h2>
                Rob Pike<br>r@golang.org<br>GTUG Sydney<br>Aug 30, 2011<br>
              </h2>
            </hgroup>
          </section>
        </div>

	<!-- start of slide 0 -->
        <div class="slide" id="slide-0">
          <header>Structural mismatch</header>

          <section>
            <p>
            Many programming problems realign one data structure to fit another structure.<br>
            </p>
            
            <ul>
            
            <li>breaking text into lines</li>
            
            <li>&#34;blocking&#34; and &#34;deblocking&#34;</li>
            
            <li>packet assembly and disassembly</li>
            
            <li>parsing</li>
            
            <li>lexing</li>
            
            </ul>
            


          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 0 --><!-- start of slide 1 -->
        <div class="slide" id="slide-1">
          <header>Sometimes hard</header>

          <section>
            <p>
            The pieces on either side have independent state, lookahead, buffers, ...<br>
            
            Can be messy to do well.<br>
            
            <br>
            
            Coroutines were invented to solve this problem!<br>
            
            They enable us to write the two pieces independently.<br>
            
            <br>
            
            Let&#39;s look at this topic in the context of a lexer.<br>
            
            <br>
            
            <br>
            </p>
            


          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 1 --><!-- start of slide 2 -->
        <div class="slide" id="slide-2">
          <header>A new template system</header>

          <section>
            <p>
            Wanted to replace the old Go template package.<br>
            
            It had many problems:<br>
            </p>
            
            <ul>
            
            <li>inflexible</li>
            
            <li>inexpressive</li>
            
            <li>code too fragile</li>
            
            </ul>
            


          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 2 --><!-- start of slide 3 -->
        <div class="slide" id="slide-3">
          <header>A new template system</header>

          <section>
            <p>
            Key change was re-engineering with a true lexer, parser,<br>
            
            and evaluator.<br>
            
            Has arbitrary text plus actions in {{ }}.<br>
            
            <br>
            </p>
            


<pre>
<!--{{code "lex/snippets" `/Evaluation/` `/Control.structures/`}}
-->Evaluation: {{.Title}}
Constants and functions: {{printf &#34;%g: %#3X&#34; 1.2+2i 123}}
Control structures {{range $s.Text}} {{.}} {{end}}
</pre>

          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 3 --><!-- start of slide 4 -->
        <div class="slide" id="slide-4">
          <header>Today we focus on the lexer</header>

          <section>
            <p>
            Must tokenize:<br>
            </p>
            
            <ul>
            
            <li>the stuff outside actions</li>
            
            <li>action delimiters</li>
            
            <li>identifiers</li>
            
            <li>numeric constants</li>
            
            <li>string constants</li>
            
            <li>and others</li>
            
            </ul>
            


          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 4 --><!-- start of slide 5 -->
        <div class="slide" id="slide-5">
          <header>Lex items</header>

          <section>
            <p>
            Two things identify each lexed item:<br>
            </p>
            
            <ul>
            
            <li>its type</li>
            
            <li>its value; a string is all we need</li>
            
            </ul>
            


<pre>
<!--{{code "lex/lex1.go" `/item.represents/` `/^}/`}}
-->// item represents a token returned from the scanner.
type item struct {
    typ itemType  // Type, such as itemNumber.
    val string    // Value, such as &#34;23.2&#34;.
}
</pre>

          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 5 --><!-- start of slide 6 -->
        <div class="slide" id="slide-6">
          <header>Lex type</header>

          <section>
            <p>
            The type is just an integer constant.<br>
            
            We use iota to define the values.<br>
            </p>
            


<pre>
<!--{{code "lex/lex1.go" `/itemType.identifies/` `/type/`}}
-->// itemType identifies the type of lex items.
type itemType int
</pre>

<pre>
<!--{{code "lex/lex1.go" `/const/` `/itemEOF/`}}
-->const (
    itemError itemType = iota // error occurred;
                              // value is text of error
    itemDot                   // the cursor, spelled &#39;.&#39;
    itemEOF
</pre>

          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 6 --><!-- start of slide 7 -->
        <div class="slide" id="slide-7">
          <header>Lex type values (continued)</header>

          <section>
            <p></p>
            


<pre>
<!--{{code "lex/lex1.go" `/itemElse/` `/^\)/`}}
-->    itemElse       // else keyword
    itemEnd        // end keyword
    itemField      // identifier, starting with &#39;.&#39;
    itemIdentifier // identifier
    itemIf         // if keyword
    itemLeftMeta   // left meta-string
    itemNumber     // number
    itemPipe       // pipe symbol
    itemRange      // range keyword
    itemRawString  // raw quoted string (includes quotes)
    itemRightMeta  // right meta-string
    itemString     // quoted string (includes quotes)
    itemText       // plain text
)
</pre>

          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 7 --><!-- start of slide 8 -->
        <div class="slide" id="slide-8">
          <header>Printing a lex item</header>

          <section>
            <p>
            Printf has a convention making it easy to print any type: just define a String() method:<br>
            
            <br>
            </p>
            


<pre>
<!--{{code "lex/lex1.go" `/func.*item.*String/` `/^}/`}}
-->func (i item) String() string {
    switch i.typ {
    case itemEOF:
        return &#34;EOF&#34;
    case itemError:
        return i.val
    }
    if len(i.val) &gt; 10 {
        return fmt.Sprintf(&#34;%.10q...&#34;, i.val)
    }
    return fmt.Sprintf(&#34;%q&#34;, i.val)
}
</pre>

          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 8 --><!-- start of slide 9 -->
        <div class="slide" id="slide-9">
          <header>How to tokenize?</header>

          <section>
            <p>
            Many approaches available:<br>
            </p>
            
            <ul>
            
            <li>use a tool such as lex or ragel</li>
            
            <li>use regular expressions</li>
            
            <li>use states, actions, and a switch statement</li>
            
            </ul>
            


          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 9 --><!-- start of slide 10 -->
        <div class="slide" id="slide-10">
          <header>Tools</header>

          <section>
            <p>
            Nothing wrong with using a tool but:<br>
            </p>
            
            <ul>
            
            <li>hard to get good errors (can be very important)</li>
            
            <li>tend to require learning another language</li>
            
            <li>result can be large, even slow</li>
            
            <li>often a poor fit</li>
            
            <li>but lexing is easy to do yourself!</li>
            
            </ul>
            


          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 10 --><!-- start of slide 11 -->
        <div class="slide" id="slide-11">
          <header>Regular expressions</header>

          <section>
            <p>
            Blogged about this last week.<br>
            </p>
            
            <ul>
            
            <li>overkill</li>
            
            <li>slow</li>
            
            <li>can explore the state space too much</li>
            
            <li>misuse of a dynamic engine to ask static questions</li>
            
            </ul>
            


          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 11 --><!-- start of slide 12 -->
        <div class="slide" id="slide-12">
          <header>Let&#39;s write our own</header>

          <section>
            <p>
            It&#39;s easy!<br>
            
            <br>
            
            Plus, most programming languages lex pretty much the same tokens, so once we learn how it&#39;s trivial to adapt the lexer for the next purpose.<br>
            
            <br>
            </p>
            
            <ul>
            
            <li>an argument both for and against tools</li>
            
            </ul>
            


          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 12 --><!-- start of slide 13 -->
        <div class="slide" id="slide-13">
          <header>State machine</header>

          <section>
            <p>
            Many people will tell you to write a switch statement,<br>
            
            something like this:<br>
            
            <br>
            </p>
            


<pre>
<!--{{code "lex/snippets" `/One/` `/^}/`}}
-->// One iteration:
switch state {
case state1: 
    state = action1()
case state2:
    state = action2()
case state3: 
    state = action3()
}
</pre>

          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 13 --><!-- start of slide 14 -->
        <div class="slide" id="slide-14">
          <header>State machines are forgetful</header>

          <section>
            <p>
            Boring and repetitive and error-prone, but anyway:<br>
            
            <br>
            
            Why switch?<br>
            
            <br>
            
            After each action, you know where you want to be;<br>
            
            the new state is the result of the action.<br>
            
            <br>
            
            But we throw the info away and recompute it from the state.<br>
            
            <br>
            
            (A consequence of returning to the caller.)<br>
            
            <br>
            
            A tool can compile that out, but so can we.<br>
            
            <br>
            </p>
            


          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 14 --><!-- start of slide 15 -->
        <div class="slide" id="slide-15">
          <header>What is a state? An action?</header>

          <section>
            <p>
            State represents where we are and what we expect.<br>
            
            <br>
            
            Action represents what we do.<br>
            
            <br>
            
            Actions result in a new state.<br>
            
            <br>
            </p>
            


          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 15 --><!-- start of slide 16 -->
        <div class="slide" id="slide-16">
          <header>State function</header>

          <section>
            <p>
            Let&#39;s put them together: a state function.<br>
            
            <br>
            
            Executes an action, returns the next state—as a state function.<br>
            
            <br>
            
            Recursive definition but simple and clear.<br>
            
            <br>
            </p>
            


<pre>
<!--{{code "lex/lex1.go" `/stateFn/` `/type/`}}
-->// stateFn represents the state of the scanner
// as a function that returns the next state.
type stateFn func(*lexer) stateFn
</pre>

          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 16 --><!-- start of slide 17 -->
        <div class="slide" id="slide-17">
          <header>The run loop</header>

          <section>
            <p>
            Our state machine is trivial:<br>
            
            just run until the state goes to nil, representing &#34;done&#34;.<br>
            
            <br>
            </p>
            


<pre>
<!--{{code "lex/snippets" `/run.lexes/` `/^}/`}}
-->// run lexes the input by executing state functions
// until the state is nil.
func run() {
    for state := startState; state != nil; {
        state = state(lexer)
    }
}
</pre>

          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 17 --><!-- start of slide 18 -->
        <div class="slide" id="slide-18">
          <header>The concurrent step</header>

          <section>
            <p>
            How do we make tokens available to the client?<br>
            
            Tokens can emerge at times that are inconvenient to stop to return to the caller.<br>
            
            <br>
            
            Use concurrency:<br>
            
            Run the state machine as a goroutine,<br>
            
            emit values on a channel.<br>
            
            <br>
            </p>
            


          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 18 --><!-- start of slide 19 -->
        <div class="slide" id="slide-19">
          <header>The lexer type</header>

          <section>
            <p>
            Here is the lexer type. Notice the channel of items; ignore the rest for now.<br>
            
            <br>
            </p>
            


<pre>
<!--{{code "lex/lex1.go" `/lexer.holds/` `/^}/`}}
-->// lexer holds the state of the scanner.
type lexer struct {
    name  string    // used only for error reports.
    input string    // the string being scanned.
    start int       // start position of this item.
    pos   int       // current position in the input.
    width int       // width of last rune read from input.
    items chan item // channel of scanned items.
}
</pre>

          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 19 --><!-- start of slide 20 -->
        <div class="slide" id="slide-20">
          <header>Starting the lexer</header>

          <section>
            <p>
            A lexer initializes itself to lex a string and launches the state machine as a goroutine, returning the lexer itself and a channel of items.<br>
            
            <br>
            
            The API will change, don&#39;t worry about it now.<br>
            </p>
            


<pre>
<!--{{code "lex/lex1.go" `/func.lex/` `/^}/`}}
-->func lex(name, input string) (*lexer, chan item) {
    l := &amp;lexer{
        name:  name,
        input: input,
        items: make(chan item),
    }
    go l.run()  // Concurrently run state machine.
    return l, l.items
}
</pre>

          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 20 --><!-- start of slide 21 -->
        <div class="slide" id="slide-21">
          <header>The real run routine</header>

          <section>
            <p>
            Here&#39;s the real state machine run function, which runs as a goroutine.<br>
            
            <br>
            </p>
            


<pre>
<!--{{code "lex/lex1.go" `/run.lexes/` `/^}/`}}
-->// run lexes the input by executing state functions until
// the state is nil.
func (l *lexer) run() {
    for state := lexText; state != nil; {
        state = state(l)
    }
    close(l.items) // No more tokens will be delivered.
}
</pre>

          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 21 --><!-- start of slide 22 -->
        <div class="slide" id="slide-22">
          <header>The token emitter</header>

          <section>
            <p>
            A token is a type and a value, but (yay Go) the value can just be sliced from the input string.<br>
            
            The lexer remembers where it is in the input and the emit routine just lobs that substring to the caller as the token&#39;s value.<br>
            
            <br>
            </p>
            


<pre>
<!--{{code "lex/lex1.go" `/input.*scanned/` `/pos.*position/`}}
-->    input string    // the string being scanned.
    start int       // start position of this item.
    pos   int       // current position in the input.
</pre>

<pre>
<!--{{code "lex/lex1.go" `/emit.passes/` `/^}/`}}
-->// emit passes an item back to the client.
func (l *lexer) emit(t itemType) {
    l.items &lt;- item{t, l.input[l.start:l.pos]}
    l.start = l.pos
}
</pre>

          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 22 --><!-- start of slide 23 -->
        <div class="slide" id="slide-23">
          <header>Starting the machine</header>

          <section>
            <p>
            As the lexer begins it&#39;s looking for plain text, so the initial state is the function lexText.<br>
            
            It absorbs plain text until a &#34;left meta&#34; is encountered.<br>
            
            <br>
            </p>
            


<pre>
<!--{{code "lex/lex1.go" `/run.lexes/` `/^}/`}}
-->// run lexes the input by executing state functions until
// the state is nil.
func (l *lexer) run() {
    for state := lexText; state != nil; {
        state = state(l)
    }
    close(l.items) // No more tokens will be delivered.
}
</pre>

<pre>
<!--{{code "lex/lex1.go" `/leftMeta/`}}
-->const leftMeta = &#34;{{&#34;
</pre>

          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 23 --><!-- start of slide 24 -->
        <div class="slide" id="slide-24">
          <header>lexText</header>

          <section>
            <p></p>
            


<pre>
<!--{{code "lex/lex1.go" `/^func.lexText/` `/^}/`}}
-->func lexText(l *lexer) stateFn {
    for {
        if strings.HasPrefix(l.input[l.pos:], leftMeta) {
            if l.pos &gt; l.start {
                l.emit(itemText)
            }
            return lexLeftMeta    // Next state.
        }
        if l.next() == eof { break }
    }
    // Correctly reached EOF.
    if l.pos &gt; l.start {
        l.emit(itemText)
    }
    l.emit(itemEOF)  // Useful to make EOF a token.
    return nil       // Stop the run loop.
}
</pre>

          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 24 --><!-- start of slide 25 -->
        <div class="slide" id="slide-25">
          <header>lexLeftMeta</header>

          <section>
            <p>
            A trivial state function.<br>
            
            When we get here, we know there&#39;s a leftMeta in the input.<br>
            
            <br>
            </p>
            


<pre>
<!--{{code "lex/lex1.go" `/^func.lexLeftMeta/` `/^}/`}}
-->func lexLeftMeta(l *lexer) stateFn {
    l.pos += len(leftMeta)
    l.emit(itemLeftMeta)
    return lexInsideAction    // Now inside {{ }}.
}
</pre>

          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 25 --><!-- start of slide 26 -->
        <div class="slide" id="slide-26">
          <header>lexInsideAction</header>

          <section>
            <p></p>
            


<pre>
<!--{{code "lex/lex1.go" `/^func.lexInsideAction/` `/itemPipe/`}}
-->func lexInsideAction(l *lexer) stateFn {
    // Either number, quoted string, or identifier.
    // Spaces separate and are ignored.
    // Pipe symbols separate and are emitted.
    for {
        if strings.HasPrefix(l.input[l.pos:], rightMeta) {
            return lexRightMeta
        }
        switch r := l.next(); {
        case r == eof || r == &#39;\n&#39;:
            return l.errorf(&#34;unclosed action&#34;)
        case isSpace(r):
            l.ignore()
        case r == &#39;|&#39;:
            l.emit(itemPipe)
</pre>

          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 26 --><!-- start of slide 27 -->
        <div class="slide" id="slide-27">
          <header>More of lexInsideAction</header>

          <section>
            <p>
            This will give you the flavor.<br>
            </p>
            


<pre>
<!--{{code "lex/lex1.go" `/case.*"/` `/lexRawQuote/`}}
-->        case r == &#39;&#34;&#39;:
            return lexQuote
        case r == &#39;`&#39;:
            return lexRawQuote
</pre>

<pre>
<!--{{code "lex/lex1.go" `/case.*9/` `/lexIdentifier/`}}
-->        case r == &#39;+&#39; || r == &#39;-&#39; || &#39;0&#39; &lt;= r &amp;&amp; r &lt;= &#39;9&#39;:
            l.backup()
            return lexNumber
        case isAlphaNumeric(r):
            l.backup()
            return lexIdentifier
</pre>

          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 27 --><!-- start of slide 28 -->
        <div class="slide" id="slide-28">
          <header>The next function</header>

          <section>
            <p></p>
            


<pre>
<!--{{code "lex/lex1.go" `/next.returns.the/` `/^}/`}}
-->// next returns the next rune in the input.
func (l *lexer) next() (rune int) {
    if l.pos &gt;= len(l.input) {
        l.width = 0
        return eof
    }
    rune, l.width =
        utf8.DecodeRuneInString(l.input[l.pos:])
    l.pos += l.width
    return rune
}
</pre>

          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 28 --><!-- start of slide 29 -->
        <div class="slide" id="slide-29">
          <header>Some lexing helpers</header>

          <section>
            <p></p>
            


<pre>
<!--{{code "lex/lex1.go" `/ignore.skips/` `/^}/`}}
-->// ignore skips over the pending input before this point.
func (l *lexer) ignore() {
    l.start = l.pos
}
</pre>

<pre>
<!--{{code "lex/lex1.go" `/backup.steps/` `/^}/`}}
-->// backup steps back one rune.
// Can be called only once per call of next.
func (l *lexer) backup() {
    l.pos -= l.width
}
</pre>

          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 29 --><!-- start of slide 30 -->
        <div class="slide" id="slide-30">
          <header>The peek function</header>

          <section>
            <p></p>
            


<pre>
<!--{{code "lex/lex1.go" `/peek.returns.but/` `/^}/`}}
-->// peek returns but does not consume
// the next rune in the input.
func (l *lexer) peek() int {
    rune := l.next()
    l.backup()
    return rune
}
</pre>

          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 30 --><!-- start of slide 31 -->
        <div class="slide" id="slide-31">
          <header>The accept functions</header>

          <section>
            <p></p>
            


<pre>
<!--{{code "lex/lex1.go" `/accept.consumes/` `/^}/`}}
-->// accept consumes the next rune
// if it&#39;s from the valid set.
func (l *lexer) accept(valid string) bool {
    if strings.IndexRune(valid, l.next()) &gt;= 0 {
        return true
    }
    l.backup()
    return false
}
</pre>

<pre>
<!--{{code "lex/lex1.go" `/acceptRun.consumes/` `/^}/`}}
-->// acceptRun consumes a run of runes from the valid set.
func (l *lexer) acceptRun(valid string) {
    for strings.IndexRune(valid, l.next()) &gt;= 0 {
    }
    l.backup()
}
</pre>

          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 31 --><!-- start of slide 32 -->
        <div class="slide" id="slide-32">
          <header>Lexing a number, including floating point</header>

          <section>
            <p></p>
            


<pre>
<!--{{code "lex/lex1.go" `/^func.lexNumber/` `/imaginary/`}}
-->func lexNumber(l *lexer) stateFn {
    // Optional leading sign.
    l.accept(&#34;+-&#34;)
    // Is it hex?
    digits := &#34;0123456789&#34;
    if l.accept(&#34;0&#34;) &amp;&amp; l.accept(&#34;xX&#34;) {
        digits = &#34;0123456789abcdefABCDEF&#34;
    }
    l.acceptRun(digits)
    if l.accept(&#34;.&#34;) {
        l.acceptRun(digits)
    }
    if l.accept(&#34;eE&#34;) {
        l.accept(&#34;+-&#34;)
        l.acceptRun(&#34;0123456789&#34;)
    }
    // Is it imaginary?
</pre>

          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 32 --><!-- start of slide 33 -->
        <div class="slide" id="slide-33">
          <header>Lexing a number, continued</header>

          <section>
            <p>
            This is more accepting than it should be, but not by much. Caller must call Atof to validate.<br>
            </p>
            


<pre>
<!--{{code "lex/lex1.go" `/Is.it.imaginary/` `/^}/`}}
-->    // Is it imaginary?
    l.accept(&#34;i&#34;)
    // Next thing mustn&#39;t be alphanumeric.
    if isAlphaNumeric(l.peek()) {
        l.next()
        return l.errorf(&#34;bad number syntax: %q&#34;,
            l.input[l.start:l.pos])
    }
    l.emit(itemNumber)
    return lexInsideAction
}
</pre>

          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 33 --><!-- start of slide 34 -->
        <div class="slide" id="slide-34">
          <header>Errors</header>

          <section>
            <p>
            Easy to handle: emit the bad token and shut down the machine.<br>
            
            <br>
            </p>
            


<pre>
<!--{{code "lex/lex1.go" `/error.returns/` `/^}/`}}
-->// error returns an error token and terminates the scan
// by passing back a nil pointer that will be the next
// state, terminating l.run.
func (l *lexer) errorf(format string, args ...interface{})
  stateFn {
    l.items &lt;- item{
        itemError,
        fmt.Sprintf(format, args...),
    }
    return nil
}
</pre>

          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 34 --><!-- start of slide 35 -->
        <div class="slide" id="slide-35">
          <header>Summary</header>

          <section>
            <p>
            Concurrency makes the lexer easy to design.<br>
            
            <br>
            
            Goroutines allow lexer and caller (parser) each to run at its own rate, as clean sequential code.<br>
            
            <br>
            
            Channels give us a clean way to emit tokens.<br>
            
            <br>
            </p>
            


          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 35 --><!-- start of slide 36 -->
        <div class="slide" id="slide-36">
          <header>A problem</header>

          <section>
            <p>
            Can&#39;t run a goroutine to completion during initialization.<br>
            
            Forbidden by the language specification.<br>
            
            (Raises awful issues about order of init, best avoided.)<br>
            
            <br>
            
            That means we can&#39;t lex &amp; parse a template during init.<br>
            
            <br>
            
            The goroutine is a problem....<br>
            
            <br>
            </p>
            


          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 36 --><!-- start of slide 37 -->
        <div class="slide" id="slide-37">
          <header>Design vs. implementation</header>

          <section>
            <p>
            ...but it&#39;s not necessary anyway.<br>
            
            <br>
            
            The work is done by the design; now we just adjust the API.<br>
            
            <br>
            
            We can change the API to hide the channel, provide a function to get the next token, and rewrite the run function.<br>
            
            <br>
            
            It&#39;s easy.<br>
            
            <br>
            </p>
            


          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 37 --><!-- start of slide 38 -->
        <div class="slide" id="slide-38">
          <header>A new API</header>

          <section>
            <p>
            Hide the channel and buffer it slightly, turning it into a ring buffer.<br>
            
            <br>
            </p>
            


<pre>
<!--{{code "lex/r59-lex.go" `/lex.creates.a.new/` `/^}/`}}
-->// lex creates a new scanner for the input string.
func lex(name, input string) *lexer {
    l := &amp;lexer{
        name:  name,
        input: input,
        state: lexText,
        items: make(chan item, 2), // Two items sufficient.
    }
    return l
}
</pre>

          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 38 --><!-- start of slide 39 -->
        <div class="slide" id="slide-39">
          <header>A function for the next item</header>

          <section>
            <p>
            Traditional lexer API: return next item.<br>
            
            Includes the modified state machine runner.<br>
            </p>
            


<pre>
<!--{{code "lex/r59-lex.go" `/nextItem.returns/` `/^}/`}}
-->// nextItem returns the next item from the input.
func (l *lexer) nextItem() item {
    for {
        select {
        case item := &lt;-l.items:
            return item
        default:
            l.state = l.state(l)
        }
    }
    panic(&#34;not reached&#34;)
}
</pre>

          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 39 --><!-- start of slide 40 -->
        <div class="slide" id="slide-40">
          <header>That&#39;s it</header>

          <section>
            <p>
            We now have a traditional API for a lexer with a simple, concurrent implementation under the covers.<br>
            
            <br>
            
            Even though the implementation is no longer truly concurrent, it still has all the advantages of concurrent design.<br>
            
            <br>
            
            We wouldn&#39;t have such a clean, efficient design if we hadn&#39;t thought about the problem in a concurrent way, without worrying about &#34;restart&#34;.<br>
            
            <br>
            
            Model completely removes concerns about &#34;structural mismatch&#34;.<br>
            
            <br>
            </p>
            


          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 40 --><!-- start of slide 41 -->
        <div class="slide" id="slide-41">
          <header>Concurrency is a design approach</header>

          <section>
            <p>
            Concurrency is not about parallelism.<br>
            
            <br>
            
            (Although it can enable parallelism).<br>
            
            <br>
            
            Concurrency is a way to design a program by decomposing it into independently executing pieces.<br>
            
            <br>
            
            The result can be clean, efficient, and very adaptable.<br>
            
            <br>
            </p>
            


          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 41 --><!-- start of slide 42 -->
        <div class="slide" id="slide-42">
          <header>Conclusion</header>

          <section>
            <p>
            Lexers are fun.<br>
            
            <br>
            
            Concurrency is fun.<br>
            
            <br>
            
            Go is fun.<br>
            
            <br>
            </p>
            


          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 42 --><!-- start of slide 43 -->
        <div class="slide" id="slide-43">
          <header>For more information</header>

          <section>
            <p>
            Go: http://golang.org<br>
            
            <br>
            
            New templates: http://golang.org/pkg/exp/template/<br>
            
            <br>
            
            (Next release will move them out of experimental.)<br>
            
            <br>
            </p>
            


          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 43 -->

        <div class="slide" id="goodbye">
          <section class="middle">
            <hgroup><img src="http://golang.org/doc/gopher/bumper640x360.png"></hgroup>
          </section>
        </div>

      </div>

      <div id="speaker-note" class="invisible" style="display: none;">
      </div> <!-- speaker note -->
      <aside id="help" class="sidebar invisible" style="display: hidden;">
        <table>
          <caption>Help</caption>
          <tbody>
            <tr>
              <th>Move Around</th>
              <td>&larr;&nbsp;&rarr;</td>
            </tr>
            <tr>
              <th>Source File</th>
              <td>s</td>
            </tr>
            <tr>
              <th>Speaker Notes</th>
              <td>n</td>
            </tr>
            <tr>
              <th>Toggle 3D</th>
              <td>3</td>
            </tr>
            <tr>
              <th>Help</th>
              <td>0</td>
            </tr>
          </tbody>
        </table>
      </aside>

    </div> <!-- presentation -->

    <!--[if lt IE 9]>
    <script 
      src="http://ajax.googleapis.com/ajax/libs/chrome-frame/1/CFInstall.min.js">
    </script>
    <script>CFInstall.check({ mode: "overlay" });</script>
    <![endif]-->

    <script src="js/utils.js"></script>
  </body>
</html>
